home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 11 / make_gri.c < prev    next >
C/C++ Source or Header  |  1987-10-08  |  8KB  |  335 lines
  1. /*----------------------------------------------------------------
  2.     make_grid
  3.     
  4.     converts graph data into a grid that can be interpreted
  5.     by hidlinpix
  6.     
  7.     William May
  8.     303A Ridgefield Circle
  9.     Clinton, MA 01510
  10.     
  11.     Feb 16, 1986        created
  12.   ----------------------------------------------------------------*/
  13.  
  14. #define DEBUG
  15.  
  16. #ifdef DEBUG
  17. #define P(x) x
  18. #else
  19. #define P(x)
  20. #endif
  21.  
  22. #include <stdio.h>
  23. #include "stack.h"
  24. #include "make_hidlin.h"
  25. #include "contour.h"
  26. #include "global.h"
  27.  
  28. extern int stack_error;
  29. extern int grid[HMAX][VMAX];
  30.  
  31. static STACK *stack;
  32.  
  33. /*------------------------------------------------------------------------
  34.     move vertically
  35.     assigning elevations to each grid point
  36.   ------------------------------------------------------------------------*/
  37. make_grid()
  38. {
  39.     register int h;
  40.         
  41.     stack = init_stack(2000);    /* should be plenty! */
  42.     
  43.     for (h = 1; h < (HMAX-1); h++) {
  44.         traverse_vert(h);
  45.     }
  46.     
  47.     del_stack(&stack);
  48. }
  49.  
  50.  
  51. /*------------------------------------------------------------------------
  52.     Traverse a vertical grid line, determining elevations along the way
  53.     This is mostly simple: i.e. keep track of the elevation of the
  54.     contour line crossed last.
  55.     The main complications are tangents (in which case we want to ignore
  56.     the contour line) and inflection points (in which case we don't
  57.     ignore the contour line).
  58.   ------------------------------------------------------------------------*/
  59. traverse_vert(h)
  60. register int h;
  61. {
  62.     register int ver, hor;
  63.     register int vmax = (VMAX - 1) * INTERVAL;
  64.     
  65.     hor = h * INTERVAL;
  66.     
  67.     push(0, stack);        /* push 0 (elev of border) onto the stack */
  68.     
  69.     P(show_line(hor,1,hor,vmax));
  70.     
  71.     for (ver = 1; ver < vmax; ver++) {
  72.         /* traverse a vertical grid line */
  73.         /* on a grid intersection set array to value on the stack */
  74.         if (!(ver % INTERVAL)) {
  75.             P(show_point(hor-3,ver));
  76.             P(show_point(hor+3,ver));
  77.             set_elevation(h, (ver / INTERVAL));
  78.         }
  79.         
  80.         /* are we crossing a contour? are we tangent to it? */
  81.         if (getpixel(hor, ver, &bmap)) {
  82.             if (is_crossing(hor, ver) || start_inflection(hor, ver))
  83.                 ver += check_hit(hor,ver);
  84.         }
  85.     }
  86. }
  87.  
  88. /*------------------------------------------------------------------------
  89.     set grid[h][v] to the value of top of stack
  90.  ------------------------------------------------------------------------*/
  91. static set_elevation(h, v)
  92. register int h, v;    /* note these are grid coordinates !! */
  93. {    
  94.     grid[h][v] = top_of_stack(stack);
  95. }
  96.  
  97. /*-----------------------------------------------------------------------
  98.        a pixel was hit, get the curve index from tree
  99.      get curve elevation from curve array
  100.      if curve elevation = elevation on stack
  101.          pop stack
  102.      else
  103.          push new elevation
  104.      end
  105.      return the number of pixels to skip-1 (i.e.
  106.      return 0 if wskip 1, etc.)
  107.  ------------------------------------------------------------------------*/
  108. static short check_hit(h, v)
  109. register int h, v;    /* note these are pixel coordinates !! */
  110. {
  111.     short    cnt = 1;    /* number of pixels */
  112.     short   ver;
  113.     
  114.     union temp {
  115.         long key;
  116.         Point p;
  117.     } temp;
  118.     LEAF *lp;
  119.     long dcmp();
  120.     int elev;
  121.     
  122.     /* traverse all pixels, if more than one */
  123.     for (ver = v+1; getpixel(h, ver++, &bmap); cnt++)
  124.         ;
  125.     
  126.     temp.p.h = h;
  127.     temp.p.v = v;
  128.     lp = find(root, temp.key, dcmp);
  129.         
  130.     elev = curves[lp->curve].elevation;
  131.         
  132.     if (elev == top_of_stack(stack))
  133.         pop(stack);
  134.     else
  135.         push(elev, stack);
  136.         
  137.     return (cnt-1);
  138. }
  139.  
  140. /*-----------------------------------------------------------------------
  141.    is_crossing: tests a point on a contour to figure out if
  142.    we are crossing the contour or tangent to the contour.  If we are
  143.    tangent to it we don't want to bump the elevation yet.
  144.    The test is performed by examining the six pixels to the side:
  145.       1     4
  146.          2 h,v 5
  147.          3     6
  148.    Crossings are:
  149.            two or more hits in range 1-6
  150.            1+ in 1-3 and 1+ in 4-6
  151.    return false for a tangent, true for a crossing.
  152.  ------------------------------------------------------------------------*/
  153. static int is_crossing(h, v)
  154. int    h, v;
  155. {
  156.     register int h_test, v_test, i;
  157.     
  158.     h_test = h - 1;    /* test the 1-3 */
  159.     v_test = v - 1;
  160.     for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  161.         ;
  162.     
  163.     if (i == 3)
  164.         return false;    /* a tangent was hit */
  165.         
  166.     h_test = h + 1;    /* test the 4-6 */
  167.     v_test = v - 1;
  168.     for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  169.         ;
  170.  
  171.     if (i == 3)
  172.         return false;    /* a tangent was hit */
  173.         
  174.     return true;        /* looks good! */
  175. }
  176.  
  177. /*-----------------------------------------------------------------------
  178.    start_inflection: tests to see if this point is the start of an
  179.    inflection in the contour. An inflection will not look like a crossing,
  180.    but should be counted as one.
  181.    An inflection looks like
  182.    
  183.           1
  184.            h,v
  185.             2
  186.             3
  187.             4
  188.              5
  189.        for example.  Only the first point on the inflection is counted.
  190.  ------------------------------------------------------------------------*/
  191. static int start_inflection(h, v)
  192. int    h, v;
  193. {
  194.     register int h_test, v_test, dir = 0, i;
  195.     
  196.     if (getpixel(h, v-1, &bmap))
  197.         return false;                /* only count the start of an inflection */
  198.         
  199.     h_test = h - 1;    /* test the 1-3 */
  200.     v_test = v - 1;
  201.     for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  202.         ;
  203.     
  204.     if (i < 3)
  205.         dir = 1;
  206.  
  207.     h_test = h + 1;    /* test the 4-6 */
  208.     v_test = v - 1;
  209.     for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  210.         ;
  211.     
  212.     if (i < 3)
  213.         dir = -1;
  214.  
  215.     if (dir == 0)
  216.         return false;        /* no inflection here */
  217.     
  218.     /*
  219.         final test: track pixels downward
  220.                     if the turn at the end is in the opposite direction
  221.                     as the original turn (indicated by dir)
  222.                     then it is an inflection
  223.     */
  224.     
  225.     v_test = v;
  226.     while (getpixel(h, v_test+1, &bmap))
  227.         v_test++;
  228.     
  229.     if (v_test != v) {
  230.         v = v_test;
  231.         
  232.         /* let's test the pixels again! */
  233.         h_test = h - 1;    /* test the 1-3 */
  234.         v_test = v - 1;
  235.         for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  236.             ;
  237.         
  238.         if (i < 3)
  239.             if (dir != 1)
  240.                 return true;    /* no change in direction, inflection */
  241.             else
  242.                 return false;    /* reversed direction, was a tangent */
  243.     
  244.         h_test = h + 1;    /* test the 4-6 */
  245.         v_test = v - 1;
  246.         for (i = 0; !getpixel(h_test, v_test, &bmap) && i < 3; i++, v_test++)
  247.             ;
  248.         
  249.         if (i < 3)
  250.             if (dir != -1)
  251.                 return true;    /* no change in direction, inflection */
  252.             else
  253.                 return false;
  254.     }
  255.     else
  256.         return false;
  257. }
  258.  
  259. #ifdef DEBUG
  260.  
  261. /*
  262.     Here is some code to display the progress of the algorithm
  263.     Fixed point math is used to speed up calculations.
  264.     Fixed point math is tricky in a typed language like C or
  265.     Pascal, and a cinch in assembly.
  266. */
  267.  
  268. #include <QuickDraw.h>
  269.  
  270. static Fixed int_to_fix(i)
  271. int i;
  272. {
  273.     asm {
  274.         move.w    i,d0    ; get the number
  275.         ext.l    d0        ; clear top of d0
  276.         swap    d0        ; make it a fixed point number, all done
  277.     }
  278. }
  279.  
  280. static int fix_to_int(i)
  281. Fixed i;
  282. {
  283.     asm {
  284.         move.l    i,d0        ; get the number
  285.         add.l    #0xA000,d0    ; add .5 to number, for rounding
  286.         swap    d0            ; make the int, ignore upper word of d0
  287.     }
  288. }
  289.  
  290. static Fixed ratio = 0x00004000;
  291.  
  292. static show_point(h,v)
  293. register int h, v;
  294. {
  295.     /*
  296.         draw each point in right window
  297.         scaled like the MacPaint draw function
  298.     */
  299.     GrafPtr oldPort;
  300.     Rect r;
  301.  
  302.     GetPort(&oldPort);
  303.     SetPort(right_wind);
  304.  
  305.     r.top    = fix_to_int(FixMul(int_to_fix(v), ratio));
  306.     r.left   = fix_to_int(FixMul(int_to_fix(h), ratio));
  307.     r.right  = r.left + 1;
  308.     r.bottom = r.top + 1;
  309.  
  310.     FrameRect(&r);
  311.     SetPort(oldPort);
  312. }
  313.  
  314. static show_line(h1,v1,h2,v2)
  315. register int h1, v1, h2, v2;
  316. {
  317.     /*
  318.         draw each line in right window
  319.         scaled like the MacPaint draw function
  320.     */
  321.     GrafPtr oldPort;
  322.  
  323.     GetPort(&oldPort);
  324.     SetPort(right_wind);
  325.  
  326.     MoveTo(fix_to_int(FixMul(int_to_fix(h1), ratio)),
  327.         fix_to_int(FixMul(int_to_fix(v1), ratio)));
  328.     LineTo(fix_to_int(FixMul(int_to_fix(h2), ratio)),
  329.         fix_to_int(FixMul(int_to_fix(v2), ratio)));
  330.  
  331.     SetPort(oldPort);
  332. }
  333.  
  334. #endif
  335.